// 插入排序 时间复杂度：平均 O(n²) 最差 O(n²) 稳定 n小时较好
/**
 *
 * @param arr{Array}
 */
function insertSort (arr) {
    let insertValue = arr[0]
    let insertIndex = 0
    for (let i = 1; i < arr.length; i++) {
        insertValue = arr[i]
        insertIndex = i - 1
        // insertIndex >= 0 保证给insertValue 找插入位置时数组不越界
        // insertValue < arr[insertIndex] 待插入的数还没找到位置
        // 就需要将arr[insertIndex]后移
        while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
            arr[insertIndex + 1] = arr[insertIndex]
            insertIndex--
        }
        // 当退出while循环 说明已经找到了插入位置
        if (insertIndex + 1 !== i) {
            arr[insertIndex + 1] = insertValue
        }
        console.log(`第${i}轮：`)
        console.log(arr)
    }
    return arr
}

function main () {
    let arr = [101, 34, 119, 1]
    insertSort(arr)
}

main()
